import copy

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        ret = []
        ret.append(0)
        acc = set(ret)
        code = ['0'] * n

        def find(code):
            #print(code)
            if len(acc)==2**n: return True

            for i in range(n)[::-1]:
                code[i] = '1' if code[i]=='0' else '0'
                codei = int(''.join(code), base=2)
                if codei not in acc:
                    ret.append(codei)
                    acc.add(codei)
                    if find(copy.copy(code)):
                        return True
                    acc.remove(codei)
                    ret.pop()
                code[i] = '1' if code[i]=='0' else '0'
        
            return False
        
        find(code)
        return ret

print(Solution().grayCode(2))